package cn.xaut.剑指offer.m10;

/**
 * 剑指 Offer 10- II. 青蛙跳台阶问题
 */
public class demo10 {

    // 动态规划
    public int numWays(int n) {

        if (n == 0 || n == 1)
            return 1;
        if (n == 2)
            return 2;
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        res[2] = 2;
        for (int i = 3; i <= n; i++) 
            res[i] = (res[i - 1] + res[i - 2]) % 1000000007;
        
        return res[n];
    }

    public static void main(String[] args) {

        System.out.println(new demo10().numWays(2));
        System.out.println(new demo10().numWays(7));
        System.out.println(new demo10().numWays(0));
    }
}
